Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1] Output: [5,6]
Example 2:
Input: nums = [1,1] Output: [2]
Constraints:
n == nums.length1 <= n <= 1051 <= nums[i] <= n
Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Average Rating: 4.79 (47 votes)
Solution
Approach 1: Using Hash Map
Intuition
The intuition behind using a hash map is pretty clear in this case. We are given that the array would be of size N and it should contain numbers from 1 to N. However, some of the numbers are missing. All we have to do is keep track of which numbers we encounter in the array and then iterate from 1⋯N and check which numbers did not appear in the hash table. Those will be our missing numbers. Let's look at a formal algorithm based on this idea and then an animation explaining the same with the help of a simple example.
Algorithm
-
Initialize a hash map,
hashto keep track of the numbers that we encounter in the array. Note that we can use asetdata structure as well in this case since we are not concerned about the frequency counts of elements.
Note that for the purposes of illustration, we have use a hash map of size 14 and have ordered the keys of the hash map from 0 to 14. Also, we will be using a simple hash function that directly maps the array entries to their corresponding keys in the hash map. Usually, the mapping is not this simple and is dependent upon the hash function being used in the implementation of the hash map.
-
Next, iterate over the given array one element at a time and for each element, insert an entry in the hash map. Even if an entry were to exist before in the hash map, it will simply be over-written. For the above example, let's look at the final state of the hash map once we process the last element of the array.
-
Now that we know the
uniqueset of elements from the array, we can simply find out the missing elements from the range 1⋯N. -
Iterate over all the numbers from 1⋯N and for each number, check if there's an entry in the hash map. If there is no entry, add that missing number to a result array that we will return from the function eventually.
Complexity Analysis
- Time Complexity : O(N)
- Space Complexity : O(N)
Approach 2: O(1) Space InPlace Modification Solution
Intuition
We definitely need to keep track of all the unique numbers that appear in the array. However, we don't want to use any extra space for it. This solution that we will look at in just a moment springs from the fact that
All the elements are in the range [1, N]
Since we are given this information, we can make use of the input array itself to somehow mark visited numbers and then find our missing numbers. Now, we don't want to change the actual data in the array but who's stopping us from changing the magnitude of numbers in the array? That is the basic idea behind this algorithm.
We will be negating the numbers seen in the array and use the sign of each of the numbers for finding our missing numbers. We will be treating numbers in the array as indices and mark corresponding locations in the array as negative.
Algorithm
- Iterate over the input array one element at a time.
- For each element
nums[i], mark the element at the corresponding location negative if it's not already marked so i.e. nums[nums[i]−1]×−1 . - Now, loop over numbers from 1⋯N and for each number check if
nums[j]is negative. If it is negative, that means we've seen this number somewhere in the array. - Add all the numbers to the resultant array which don't have their corresponding locations marked as negative in the original array.
Complexity Analysis
- Time Complexity : O(N)
- Space Complexity : O(1) since we are reusing the input array itself as a hash table and the space occupied by the output array doesn't count toward the space complexity of the algorithm.
May 14, 2020 7:26 AM
I like this question.
But the optimal solution is like one of those either you get it right away, or you need some hint.
December 26, 2019 11:26 PM
Swapping Solution, O(n) runtime, O(1) space:
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for(int i = 0; i < nums.length; i++){
int idx = nums[i]-1;
// swap until the nums[i] is at index nums[i]-1
while(idx != nums[i]){
swap(nums, idx, i);
idx = nums[i] - 1;
// if we are going to swap same number: break
if(nums[idx] == nums[i]){
break;
}
}
}
// In this point, the array looks like this: [1,2,3,4,3,2,7,8]
List<Integer> res = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
if(i != nums[i]-1){
res.add(i+1);
}
}
return res;
}
private void swap(int[] nums, int idx1, int idx2){
int temp = nums[idx1];
nums[idx1] = nums[idx2];
nums[idx2] = temp;
}
}
August 20, 2020 2:57 AM
Hmmm.... I feel like this problem could be a medium if it didn't allow anything above O(1) space.
January 2, 2021 11:37 PM
In the 2nd approach, the existing input array is modified and before returning we are not reverting the changes back. Is it okay?
And in real life development, will it be considered a good practice to modify the present data in order to save space?
Last Edit: December 28, 2020 7:23 PM
Personally, I don't find the last approach any smart or useful. Even, it hurts my eyes.
You are basically using the input space as the hash map. There is nothing fancy about it. I would not think of this way because I would never hold my data in such a confusing way. Or, I would not ever mess with the input data/space.
When you make use of the input space to store data, you are technically using the extra space even though you put the original data back. It is like you borrow money from a bank to run a business and telling people that you are running a business for free. Maybe, if you have good credit, you might end up spending no money out of your poker, but, over all, running a business costs money.
How is this kind of solution ever useful or maintainable in production? I truly hope that none of the interviewers, companies, or coding practice platforms ever advocate bad coding practice.
May 14, 2020 6:05 PM
Python 4-liner O(n) runtime with O(1) space using swapping (without negating, IMHO clearer solution)
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for idx in range(len(nums)):
while nums[nums[idx]-1] != nums[idx]: # value at target index misplaced
nums[nums[idx]-1], nums[idx] = nums[idx], nums[nums[idx]-1] # swap
return [idx+1 for idx, num in enumerate(nums) if num != idx + 1]
Last Edit: January 6, 2021 5:14 PM
Python 1 liner. O(n) time and space complexity
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
# 1-liner solution
return set(range(1,len(nums)+1)) - set(nums)
August 26, 2020 11:44 AM
Getting to think negating the numbers will not come in first shot though as the original array is being modified.
Negating the numbers is same as modifying the contents of array - so might not be a neat solution.
Last Edit: October 28, 2019 1:01 AM
This is just a set difference {1...n} - {nums} = {missing numbers}. Here's an easy solution in JavaScript:
var findDisappearedNumbers = function(nums) {
let range = [];
for (let i = 0; i < nums.length;i++) range.push(i+1);
return range.filter(x => nums.indexOf(x) < 0);
};
September 15, 2020 12:02 PM
C++ solution with 2 FOR loops.
First swap elements which are not in their intended place.
Finally check the missing elements
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
bool modified = true;
while(modified) {
modified = false;
for (int i=0; i<nums.size(); i++) {
if ((nums[i] != i+1) && (nums[i] != nums[nums[i]-1])) {
swap(nums[i], nums[nums[i]-1]);
modified = true;
}
}
}
vector<int> res;
for (int i=0; i<nums.size(); i++) {
if (nums[i] != i+1)
res.push_back(i+1);
}
return res;
}
};
xxxxxxxxxxclass Solution {public: vector<int> findDisappearedNumbers(vector<int>& nums) { }};